#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=205;
struct Edge{
    int v,next;
}edges[N<<1];
int head[N];
int cnt;
int n,m;
int dp[N][N];
void init(){
    cnt=0;
    memset(head,-1,sizeof(head));
    memset(dp,0,sizeof(dp));
}
void addEdge(int s,int e){
    edges[cnt].v=e;
    edges[cnt].next=head[s];
    head[s]=cnt++;
}
void dfs(int u){
    for(int i=head[u];i!=-1;i=edges[i].next){
        int v=edges[i].v;
        dfs(v);
        if(u==0){
            for(int l=m;l>=0;l--){
                //u是根节点，所以子节点可以选全部k个
                for(int k=1;k<=l;k++){
                    //选l个分为从父节点开始选l-k个 子节点开始选k个
                    dp[u][l]=max(dp[u][l],dp[u][l-k]+dp[v][k]);
                }
            }
        }
        else{
            for(int l=m;l>=0;l--){
                for(int k=1;k<l;k++){
                    dp[u][l]=max(dp[u][l],dp[u][l-k]+dp[v][k]);
                }
            }
        }
    }
}
int main(void){
    //freopen("data.txt","r",stdin);
    int s,v;
    while(~scanf("%d%d",&n,&m)){
        if(n==0 && m==0){
            break;
        }
        init();
        for(int i=1;i<=n;i++){
            scanf("%d%d",&s,&v);
            //先攻克s才能攻克i
            addEdge(s,i);
            dp[i][1]=v;
        }
        //0作为根节点
        dfs(0);
        //dp[0][m]表示从0开始取m个节点的最大值
        printf("%d\n",dp[0][m]);
    }
    return 0;
}